package com.sevent;

import java.net.ServerSocket;
import java.util.HashSet;
import java.util.Set;

/**
 * 1.输出合法的括号组合
 * 输入括号对数
 * 输出所有合法组合
 * 输入:3
 * 输出:()()(),((())),(()()),()(()),(())(),
 * 2.判断一个字符串是否合法
 */

public class 题目三_括号题目 {
    public static void main(String[] args) {
        System.out.println(parenthesis(3));
        System.out.println(parenthesis1(3));
    }

    public static Set<String> parenthesis(int n) {
        Set<String> s_n = new HashSet<>();
        if (n == 1) {
            s_n.add("()");
            return s_n;
        }
        Set<String> s_n_1 = parenthesis(n - 1);
        for (String eOFN_1 : s_n_1) {
            s_n.add("()" + eOFN_1);
            s_n.add(eOFN_1 + "()");
            s_n.add("(" + eOFN_1 + ")");
        }
        return s_n;
    }

    public static Set<String> parenthesis1(int n) {
        Set<String> res = new HashSet<>();
        res.add("()");
        if (n == 1) {
            return res;
        }
        for (int i = 2; i <= n; i++) {
            Set<String> new_set = new HashSet<>();

            for(String e: res){
                new_set.add("()" + e);
                new_set.add(e + "()");
                new_set.add("(" + e + ")");
            }
            res = new_set;
        }
        return res;
    }
}
